List of algorithms
The following is a list of algorithms along with one-line descriptions for each. Combinatorial algorithms General combinatorial algorithms * Brent's algorithm: finds cycles in iterations using only two iterators * Floyd's cycle-finding algorithm: finds cycles in iterations * Gale–Shapley algorithm: solve the stable marriage problem * Pseudorandom number generators (uniformly distributed): ** Blum Blum Shub ** Lagged Fibonacci generator ** Linear congruential generator ** Mersenne twister Graph algorithms * Coloring algorithm: Graph coloring algorithm. * Hopcroft–Karp algorithm: convert a bipartite graph to a maximum cardinality matching * Hungarian algorithm: algorithm for finding a perfect matching * Prüfer coding: conversion between a labeled tree and its Prüfer sequence * Tarjan's off-line least common ancestors algorithm: compute lowest common ancestors for pairs of nodes in a tree * Topological sort: finds linear order of nodes(e.g. jobs) based on their dependencies. Graph drawing * Force-based algorithms (also known as force-directed algorithms or spring-based algorithm) * Spectral layout Network theory * Network analysis ** Link analysis *** Girvan–Newman algorithm: detect communities in complex systems *** Web link analysis **** Hyperlink-Induced Topic Search (HITS) (also known as Hubs and authorities) **** PageRank **** TrustRank **** PRW, PFW * Flow networks ** Dinic's algorithm: is a strongly polynomial algorithm for computing the maximum flow in a flow network. ** Edmonds–Karp algorithm: implementation of Ford–Fulkerson ** Ford–Fulkerson algorithm: computes the maximum flow in a graph ** Karger's algorithm: a Monte Carlo method to compute the minimum cut of a connected graph ** Push-relabel algorithm: computes a maximum flow in a graph Routing * Edmonds's algorithm (also known as Chu–Liu/Edmonds's algorithm): find maximum or minimum branchings * Euclidean minimum spanning tree: algorithms for computing the minimum spanning tree of a set of points in the plane * Longest path problem: find a simple path of maximum length in a given graph * Minimum spanning tree ** Boruvka's algorithm ** Kruskal's algorithm ** Prim's algorithm ** Reverse-delete algorithm * Nonblocking Minimal Spanning Switch say, for a telephone exchange * Shortest path problem ** Bellman–Ford algorithm: computes shortest paths in a weighted graph (where some of the edge weights may be negative) ** Dijkstra's algorithm: computes shortest paths in a graph with non-negative edge weights ** Floyd–Warshall algorithm: solves the all pairs shortest path problem in a weighted, directed graph ** Johnson algorithm: All pairs shortest path algorithm in sparse weighted directed graph ** Perturbation methods: an algorithm that computes a locally shortest paths in a graph * Traveling salesman problem ** Christofides algorithm ** Nearest neighbour algorithm Search * A*: special case of best-first search that uses heuristics to improve speed * B*: a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals) * Backtracking: abandon partial solutions when they are found not to satisfy a complete solution * Beam search: is a heuristic search algorithm that is an optimization of best-first search that reduces its memory requirement * Beam stack search: integrates backtracking with beam search * Best-first search: traverses a graph in the order of likely importance using a priority queue * Bidirectional search: find the shortest path from an initial vertex to a goal vertex in a directed graph * Bloom filter: a constant time and memory check to see whether a given element exists in a set. May return a false positive, but never a false negative. * Breadth-first search: traverses a graph level by level * D*: an incremental heuristic search algorithm * Depth-first search: traverses a graph branch by branch * Iterative deepening depth-first search (IDDFS): a state space search strategy * Lexicographic breadth-first search (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph * Uniform-cost search: a tree search that finds the lowest cost route where costs vary * SSS*: state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm Subgraphs * Bron–Kerbosch algorithm: a technique for finding maximal cliques in an undirected graph * Strongly connected components ** Cheriyan–Mehlhorn/Gabow algorithm ** Kosaraju's algorithm ** Tarjan's algorithm Sequence algorithms Approximate matching * Bitap algorithm: fuzzy algorithm that determines if strings are approximately equal. * Phonetic algorithms ** Daitch–Mokotoff Soundex: a Soundex refinement which allows matching of Slavic and Germanic surnames ** Double Metaphone: an improvement on Metaphone ** Match Rating Approach: a phonetic algorithm developed by Western Airlines ** Metaphone: an algorithm for indexing words by their sound, when pronounced in English ** NYSIIS: phonetic algorithm, improves on Soundex ** Soundex: a phonetic algorithm for indexing names by sound, as pronounced in English * String metrics: compute a similarity or dissimilarity (distance) score between two pairs of text strings ** Damerau–Levenshtein distance compute a distance measure between two strings, improves on Levenshtein distance ** Dice's coefficient (also known as the Dice coefficient): a similarity measure related to the Jaccard index ** Hamming distance: sum number of positions which are different ** Jaro–Winkler distance: is a measure of similarity between two strings ** Levenshtein edit distance: compute a metric for the amount of difference between two sequences * Trigram search: search for text when the exact syntax or spelling of the target object is not precisely known Item search * Linear search: finds an item in an unsorted list * Selection algorithm: finds the k''th largest item in a list * Sorted lists ** Binary search algorithm: locates an item in a sorted list ** Fibonacci search technique: search a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers ** Jump search (also called block search) ** Predictive search: binary-like search which factors in magnitude of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search. ** Uniform binary search: an optimization of the classic binary search algorithm * Ternary search: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa Merging * Simple Merge algorithm * k-way Merge algorithm * Union (merge, with elements on the output not repeated) Permutations * Fisher–Yates shuffle (also known as the Knuth shuffle): randomly shuffle a finite set * Robinson–Schensted algorithm: generates permutations from pairs of Young tableaux * Steinhaus–Johnson–Trotter algorithm (also known as the Johnson–Trotter algorithm): generate permutations by transposing elements Sequence alignment * Dynamic time warping: measure similarity between two sequences which may vary in time or speed * Hirschberg's algorithm: finds the least cost sequence alignment between two sequences, as measured by their Levenshtein distance * Needleman–Wunsch algorithm: find global alignment between two sequences * Smith–Waterman algorithm: find local sequence alignment Sorting * Exchange Sorts ** Bubble sort: for each pair of indices, swap the items if out of order ** Cocktail sort ** Comb sort ** Gnome sort ** Odd-even sort ** Quicksort: divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Often the method of choice * Humorous or ineffective ** Bogosort ** Stooge sort * Hybrid ** Flashsort ** Introsort: begin with quicksort and switch to heapsort when the recursion depth exceeds a certain level ** Timsort: adaptative algorithm derived from merge sort and insertion sort. Used in Python >=2.3 and Java SE 7. * Insertion sorts ** Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there ** Library sort ** Patience sorting ** Shell sort: an attempt to improve insertion sort ** Tree sort (binary tree sort): build binary tree, then traverse it to create sorted list ** Cycle sort: in-place with theoretically optimal number of writes * Merge sorts ** Merge sort: sort the first and second half of the list separately, then merge the sorted lists ** Strand sort * Non-comparison sorts ** Bead sort ** Bucket sort ** Burstsort: build a compact, cache efficient burst trie and then traverse it to create sorted output ** Counting sort ** Pigeonhole sort ** Postman sort: variant of Bucket sort which takes advantage of hierarchical structure ** Radix sort: sorts strings letter by letter * Selection sorts ** Heapsort: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list ** Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list ** Smoothsort * Other ** Bitonic sorter ** Pancake sorting ** Topological sort * Unknown class ** Samplesort Subsequences *Kadane's algorithm: finds maximum sub-array of any size *Longest common subsequence problem: Find the longest subsequence common to all sequences in a set of sequences *Longest increasing subsequence problem: find the longest increasing subsequence of a given sequence *Shortest common supersequence problem: Find the shortest supersequence that contains two or more sequences as subsequences Substrings * Longest common substring problem: find the longest string (or strings) that is a substring (or are substrings) of two or more strings * Substring search ** Aho–Corasick string matching algorithm: trie based algorithm for finding all substring matches to any of a finite set of strings ** Boyer–Moore string search algorithm: amortized linear (sublinear in most times) algorithm for substring search ** Boyer–Moore–Horspool algorithm: Simplification of Boyer–Moore ** Knuth–Morris–Pratt algorithm: substring search which bypasses reexamination of matched characters ** Rabin–Karp string search algorithm: searches multiple patterns efficiently ** Zhu–Takaoka string matching algorithm: a variant of the Boyer–Moore * Ukkonen's algorithm: a linear-time, online algorithm for constructing suffix trees Computational mathematics Abstract algebra * Chien search: a recursive algorithm for determining roots of polynomials defined over a finite field * Schreier–Sims algorithm: computing a base and strong generating set (BSGS) of a permutation group * Todd–Coxeter algorithm: Procedure for generating cosets. Computer algebra * Buchberger's algorithm: finds a Gröbner basis * Cantor–Zassenhaus algorithm: factor polynomials over finite fields * Faugère F4 algorithm: finds a Gröbner basis (also mentions the F5 algorithm) * Gosper's algorithm: find sums of hypergeometric terms that are themselves hypergeometric terms * Knuth–Bendix completion algorithm: for rewriting rule systems * Multivariate division algorithm: for polynomials in several indeterminates * Pollard's kangaroo algorithm (also known as Pollard's lambda algorithm ): an algorithm for solving the discrete logarithm problem * Polynomial long division: an algorithm for dividing a polynomial by another polynomial of the same or lower degree * Risch algorithm: an algorithm for the calculus operation of indefinite integration (i.e. finding antiderivatives) Geometry * Closest pair problem: find the pair of points (from a set of points) with the smallest distance between them * Collision detection algorithms: check for the collision or intersection of two given solids * Cone algorithm: identify surface points * Convex hull algorithms: determining the convex hull of a set of points ** Chan's algorithm ** Gift wrapping algorithm or Jarvis march ** Graham scan ** Kirkpatrick–Seidel algorithm * Euclidean Distance Transform - Computes the distance between every point in a grid and a discrete collection of points. * Geometric hashing: a method for efficiently finding two-dimensional objects represented by discrete points that have undergone an affine transformation * Gilbert–Johnson–Keerthi distance algorithm: determining the smallest distance between two convex shapes. * Jump-and-Walk algorithm: an algorithm for point location in triangulations * Laplacian smoothing: an algorithm to smooth a polygonal mesh * Line segment intersection: finding whether lines intersect, usually with a sweep line algorithm ** Bentley–Ottmann algorithm ** Shamos–Hoey algorithm * Minimum bounding box algorithms: find the oriented minimum bounding box enclosing a set of points * Nearest neighbor search: find the nearest point or points to a query point * Point in polygon algorithms: tests whether a given point lies within a given polygon * Rotating calipers: determine all antipodal pairs of points and vertices on a convex polygon or convex hull. * Shoelace algorithm: determine the area of a polygon whose vertices are described by ordered pairs in the plane * Triangulation ** Delaunay triangulation *** Ruppert's algorithm (also known as Delaunay refinement): create quality Delaunay triangulations *** Chew's second algorithm: create quality constrained Delaunay triangulations ** Marching triangles: reconstruct two-dimensional surface geometry from an unstructured point cloud ** Polygon triangulation algorithms: decompose a polygon into a set of triangles ** Voronoi diagrams, geometric dual of Delaunay triangulation *** Bowyer–Watson algorithm: create voronoi diagram in any number of dimensions *** Fortune's Algorithm: create voronoi diagram Number theoretic algorithms * Binary GCD algorithm: Efficient way of calculating GCD. * Booth's multiplication algorithm * Chakravala method: a cyclic algorithm to solve indeterminate quadratic equations, including Pell's equation * Discrete logarithm: ** Baby-step giant-step ** Index calculus algorithm ** Pollard's rho algorithm for logarithms ** Pohlig–Hellman algorithm * Euclidean algorithm: computes the greatest common divisor * Extended Euclidean algorithm: Also solves the equation ''ax + by = c''. * Integer factorization: breaking an integer into its prime factors ** Congruence of squares ** Dixon's algorithm ** Fermat's factorization method ** General number field sieve ** Lenstra elliptic curve factorization ** [[Pollard's p − 1 algorithm|Pollard's ''p − 1 algorithm]] ** Pollard's rho algorithm ** prime factorization algorithm ** Quadratic sieve ** Shor's algorithm ** Special number field sieve ** Trial division * Multiplication algorithms: fast multiplication of two numbers ** Karatsuba algorithm ** Schönhage–Strassen algorithm ** Toom–Cook multiplication * Odlyzko–Schönhage algorithm: calculates nontrivial zeroes of the Riemann zeta function * Primality tests: determining whether a given number is prime ** AKS primality test ** Fermat primality test ** Lucas primality test ** Miller–Rabin primality test ** Sieve of Atkin ** Sieve of Eratosthenes ** Sieve of Sundaram Numerical algorithms Elementary and special functions * Computation of π: ** Borwein's algorithm: an algorithm to calculate the value of 1/π ** Gauss–Legendre algorithm: computes the digits of pi ** Bailey–Borwein–Plouffe formula: (BBP formula) a spigot algorithm for the computation of the nth binary digit of π * Hyperbolic and Trigonometric Functions: ** BKM algorithm: compute elementary functions using a table of logarithms ** CORDIC: compute hyperbolic and trigonometric functions using a table of arctangents * Exponentiation: ** Addition-chain exponentiation exponentiation by positive integer powers that requires a minimal number of multiplications ** Exponentiating by squaring: an algorithm used for the fast computation of large integer powers of a number * Montgomery reduction: an algorithm that allows modular arithmetic to be performed efficiently when the modulus is large * Multiplication algorithms: fast multiplication of two numbers ** Booth's multiplication algorithm: a multiplication algorithm that multiplies two signed binary numbers in two's complement notation ** Fürer's algorithm: an integer multiplication algorithm for very large numbers possessing a very low asymptotic complexity ** Karatsuba algorithm: an efficient procedure for multiplying large numbers ** Schönhage–Strassen algorithm: an asymptotically fast multiplication algorithm for large integers ** Toom–Cook multiplication: (Toom3) a multiplication algorithm for large integers * Rounding functions: the classic ways to round numbers * Spigot algorithm: A way to compute the value of a mathematical constant without knowing preceding digits * Square and Nth root of a number: ** Alpha max plus beta min algorithm: an approximation of the square-root of the sum of two squares ** Methods of computing square roots ** ''n''th root algorithm ** Shifting nth-root algorithm: digit by digit root extraction * Summation: ** Binary splitting: a divide and conquer technique which speeds up the numerical evaluation of many types of series with rational terms ** Kahan summation algorithm: a more accurate method of summing floating-point numbers Geometric * Filtered back-projection: efficiently compute the inverse 2-dimensional Radon transform. * Level set method (LSM): a numerical technique for tracking interfaces and shapes Interpolation and extrapolation * Birkhoff interpolation: an extension of polynomial interpolation * Cubic interpolation * Hermite interpolation * Linear interpolation: a method of curve fitting using linear polynomials * Monotone cubic interpolation: a variant of cubic interpolation that preserves monotonicity of the data set being interpolated. * Multivariate interpolation ** Bicubic interpolation, a generalization of cubic interpolation to two dimensions ** Bilinear interpolation: an extension of linear interpolation for interpolating functions of two variables on a regular grid ** Lanczos resampling ("Lanzosh"): a multivariate interpolation method used to compute new values for any digitally sampled data ** Nearest-neighbor interpolation ** Tricubic interpolation, a generalization of cubic interpolation to three dimensions * Pareto interpolation: a method of estimating the median and other properties of a population that follows a Pareto distribution. * Polynomial interpolation ** Neville's algorithm * Spline interpolation: Reduces error with Runge's phenomenon. ** De Boor algorithm: B-splines ** De Casteljau's algorithm: Bézier splines * Trigonometric interpolation Linear algebra * Eigenvalue algorithms ** Arnoldi iteration ** Inverse iteration ** Jacobi method ** Lanczos iteration ** QR algorithm ** Rayleigh quotient iteration * Gram–Schmidt process: orthogonalizes a set of vectors * Matrix multiplication ** Cannon's algorithm: a distributed algorithm for matrix multiplication especially suitable for computers laid out in an N × N mesh ** Coppersmith–Winograd algorithm: square matrix multiplication ** Freivald's algorithm: a randomized algorithm used to verify matrix multiplication ** Strassen algorithm: faster matrix multiplication * Solving systems of linear equations ** Biconjugate gradient method: solves systems of linear equations ** Conjugate gradient: an algorithm for the numerical solution of particular systems of linear equations ** Gaussian elimination ** Gauss–Jordan elimination: solves systems of linear equations ** Gauss–Seidel method: solves systems of linear equations iteratively ** Levinson recursion: solves equation involving a Toeplitz matrix ** Stone's method: also known as the strongly implicit procedure or SIP, is an algorithm for solving a sparse linear system of equations ** Successive over-relaxation (SOR): method used to speed up convergence of the Gauss–Seidel method ** Tridiagonal matrix algorithm (Thomas algorithm): solves systems of tridiagonal equations * Sparse matrix algorithms ** Cuthill–McKee algorithm: reduce the bandwidth of sparse symmetric matrices ** Minimum degree algorithm: permute the rows and columns of a symmetric sparse matrix before applying the Cholesky decomposition ** Symbolic Cholesky decomposition: Efficient way of storing sparse matrix Monte Carlo * Gibbs sampling: generate a sequence of samples from the joint probability distribution of two or more random variables * Metropolis–Hastings algorithm: used to generate a sequence of samples from the probability distribution of one or more variables * Wang and Landau algorithm: an extension of Metropolis–Hastings algorithm sampling Numerical integration * MISER algorithm: Monte Carlo simulation, numerical integration * Multigrid methods: (MG methods): a group of algorithms for solving differential equations using a hierarchy of discretizations * Verlet integration ( ): integrate Newton's equations of motion Root finding * False position method: approximates roots of a function * Newton's method: finds zeros of functions with calculus * Secant method: approximates roots of a function Optimization algorithms * Alpha-beta pruning: search to reduce number of nodes in minimax algorithm * Branch and bound * Chain matrix multiplication * Combinatorial optimization: optimization problems where the set of feasible solutions is discrete ** Greedy randomized adaptive search procedure (GRASP): successive constructions of a greedy randomized solution and subsequent iterative improvements of it through a local search ** Hungarian method: a combinatorial optimization algorithm which solves the assignment problem in polynomial time * Constraint satisfaction ** General algorithms for the constraint satisfaction *** AC-3 algorithm *** Difference map algorithm *** Min conflicts algorithm ** Chaff algorithm: an algorithm for solving instances of the boolean satisfiability problem ** Davis–Putnam algorithm: check the validity of a first-order logic formula ** Davis–Putnam–Logemann–Loveland algorithm (DPLL): an algorithm for deciding the satisfiability of propositional logic formula in conjunctive normal form, i.e. for solving the CNF-SAT problem ** Exact cover problem *** Algorithm X: a nondeterministic algorithm *** Dancing Links: an efficient implementation of Algorithm X * Cross-entropy method: a general Monte Carlo approach to combinatorial and continuous multi-extremal optimization and importance sampling * Differential evolution * Dynamic Programming: problems exhibiting the properties of overlapping subproblems and optimal substructure * Ellipsoid method: is an algorithm for solving convex optimization problems * Evolutionary computation: optimization inspired by biological mechanisms of evolution ** Evolution strategy ** Genetic algorithms *** Fitness proportionate selection - also known as roulette-wheel selection *** Stochastic universal sampling *** Truncation selection *** Tournament selection ** Memetic algorithm ** Swarm intelligence *** Ant colony optimization *** Bees algorithm: a search algorithm which mimics the food foraging behavior of swarms of honey bees *** Particle swarm * Gradient descent * Harmony search (HS): a metaheuristic algorithm mimicking the improvisation process of musicians * Interior point method * Linear programming ** Dantzig–Wolfe decomposition: an algorithm for solving linear programming problems with special structure ** Delayed column generation ** Integer linear programming: solve linear programming problems where some or all the unknowns are restricted to integer values *** Branch and cut *** Cutting-plane method ** Karmarkar's algorithm: The first reasonably efficient algorithm that solves the linear programming problem in polynomial time. ** Simplex algorithm: An algorithm for solving the linear programming problem * Line search * Local search: a metaheuristic for solving computationally hard optimization problems ** Random-restart hill climbing ** Tabu search * Minimax used in game programming * Nearest neighbor search (NNS): find closest points in a metric space ** Best Bin First: find an approximate solution to the Nearest neighbor search problem in very high dimensional spaces * Newton's method in optimization * Nonlinear optimization ** BFGS method: A nonlinear optimization algorithm ** Gauss–Newton algorithm: An algorithm for solving nonlinear least squares problems. ** Levenberg–Marquardt algorithm: An algorithm for solving nonlinear least squares problems. ** Nelder–Mead method (downhill simplex method): A nonlinear optimization algorithm * Odds algorithm (Bruss algorithm) : Finds the optimal strategy to predict a last specific event in a random sequence event * Simulated annealing * Stochastic tunneling * Subset sum algorithm Computational science Astronomy * Doomsday algorithm: day of the week * Zeller's congruence is an algorithm to calculate the day of the week for any Julian or Gregorian calendar date * various Easter algorithms are used to calculate the day of Easter Bioinformatics * Basic Local Alignment Search Tool also known as BLAST: an algorithm for comparing primary biological sequence information * Kabsch algorithm: calculate the optimal alignment of two sets of points in order to compute the root mean squared deviation between two protein structures. * Velvet: a set of algorithms manipulating de Bruijn graphs for genomic sequence assembly Geoscience * Vincenty's formulae: a fast algorithm to calculate the distance between two latitude/longitude points on an ellipsoid Linguistics * Lesk algorithm: word sense disambiguation * Stemming algorithm: a method of reducing words to their stem, base, or root form * Sukhotins Algorithm: a statistical classification algorithm for classifying characters in a text as vowels or consonants Medicine * ESC algorithm for the diagnosis of heart failure * Manning Criteria for irritable bowel syndrome * Pulmonary embolism diagnostic algorithms * Texas Medication Algorithm Project Physics * Constraint algorithm: a class of algorithms for satisfying constraints for bodies that obey Newton's equations of motion * Demon algorithm: a Monte Carlo method for efficiently sampling members of a microcanonical ensemble with a given energy * Featherstone's algorithm: compute the effects of forces applied to a structure of joints and links * Fast multipole method (FMM): speed up the calculation of long-ranged forces in the n-body problem * Rainflow-counting algorithm: Reduces a complex stress history to a count of elementary stress-reversals for use in fatigue analysis * Sweep and prune: a broad phase algorithm used during collision detection to limit the number of pairs of solids that need to be checked for collision * VEGAS algorithm: a method for reducing error in Monte Carlo simulations Statistics * Algorithms for calculating variance: avoiding instability and numerical overflow * Approximate counting algorithm: Allows counting large number of events in a small register * Bayesian statistics ** Nested sampling algorithm: a computational approach to the problem of comparing models in Bayesian statistics * Clustering Algorithms ** Canopy clustering algorithm: an unsupervised clustering algorithm related to the K-means algorithm ** DBSCAN: a density based clustering algorithm ** Expectation-maximization algorithm ** Fuzzy clustering: a class of clustering algorithms where each point has a degree of belonging to clusters *** Fuzzy c-means *** FLAME clustering (Fuzzy clustering by Local Approximation of MEmberships): define clusters in the dense parts of a dataset and perform cluster assignment solely based on the neighborhood relationships among objects ** k-means algorithm: cluster objects based on attributes into partitions ** k-medoids: similar to k-means, but chooses datapoints or medoids as centers ** Linde–Buzo–Gray algorithm: a vector quantization algorithm to derive a good codebook ** Lloyd's algorithm (Voronoi iteration or relaxation): group data points into a given number of categories. ** OPTICS: a density based clustering algorithm with a visual evaluation method ** Single-linkage clustering: a simple agglomerative clustering algorithm ** QT clustering: partitions without the number of clusters a priori * Estimation Theory ** Expectation-maximization algorithm A class of related algorithms for finding maximum likelihood estimates of parameters in probabilistic models *** Ordered subset expectation maximization (OSEM): used in medical imaging for positron emission tomography, single photon emission computed tomography and X-ray computed tomography. ** Odds algorithm (Bruss algorithm) Optimal online search for distinguished value in sequential random input ** Kalman filter: estimate the state of a dynamic system from a series of noisy measurements * False nearest neighbor algorithm (FNN) estimates fractal dimension * Hidden Markov model ** Baum–Welch algorithm: compute maximum likelihood estimates and posterior mode estimates for the parameters of a hidden markov model ** Forward-backward algorithm a dynamic programming algorithm for computing the probability of a particular observation sequence ** Viterbi algorithm: find the most likely sequence of hidden states in a hidden markov model * Partial least squares regression: finds a linear model describing some predicted variables in terms of other observable variables * Queuing theory ** Buzen's algorithm: an algorithm for calculating the normalization constant G(K) in the Gordon–Newell theorem * RANSAC (an abbreviation for "RANdom SAmple Consensus"): an iterative method to estimate parameters of a mathematical model from a set of observed data which contains outliers * Scoring algorithm: is a form of Newton's method used to solve maximum likelihood equations numerically * Yamartino method: calculate an approximation to the standard deviation σθ of wind direction θ during a single pass through the incoming data * Ziggurat algorithm: generate random numbers from a non-uniform distribution Computer science Computer architecture * Tomasulo algorithm: allows sequential instructions that would normally be stalled due to certain dependencies to execute non-sequentially Computer graphics * Clipping ** Line clipping *** Cohen–Sutherland *** Cyrus–Beck *** Fast-clipping *** Liang–Barsky *** Nicholl–Lee–Nicholl ** Polygon clipping *** Sutherland–Hodgman *** Vatti *** Weiler–Atherton * Contour lines and Isosurfaces ** Marching cubes: extract a polygonal mesh of an isosurface from a three-dimensional scalar field (sometimes called voxels) ** Marching squares: generate contour lines for a two-dimensional scalar field ** Marching tetrahedrons: an alternative to Marching cubes * Discrete Green's Theorem: is an algorithm for computing double integral over a generalized rectangular domain in constant time. It is a natural extension to the summed area table algorithm * Flood fill: fills a connected region of a multi-dimensional array with a specified symbol * Global illumination algorithms: Considers direct illumination and reflection from other objects. ** Ambient occlusion ** Beam tracing ** Cone tracing ** Image-based lighting ** Metropolis light transport ** Path tracing ** Photon mapping ** Radiosity ** Ray tracing * Hidden surface removal or Visual surface determination ** Newell's algorithm: eliminate polygon cycles in the depth sorting required in hidden surface removal ** Painter's algorithm: detects visible parts of a 3-dimensional scenery ** Scanline rendering: constructs an image by moving an imaginary line over the image ** Warnock algorithm * Line Drawing: graphical algorithm for approximating a line segment on discrete graphical media. ** Bresenham's line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses decision variables) ** DDA line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses floating-point math) ** Xiaolin Wu's line algorithm: algorithm for line antialiasing. * Midpoint circle algorithm: an algorithm used to determine the points needed for drawing a circle * Ramer–Douglas–Peucker algorithm: Given a 'curve' composed of line segments to find a curve not too dissimilar but that has fewer points * Shading ** Gouraud shading: an algorithm to simulate the differing effects of light and colour across the surface of an object in 3D computer graphics ** Phong shading: an illumination model and an interpolation method in 3D computer graphics * Slerp (spherical linear interpolation): quaternion interpolation for the purpose of animating 3D rotation * Summed Area Table (also known as an Integral Image): is an algorithm for computing sum of values in a rectangular subset of a grid in constant time Cryptography * Asymmetric (public key) encryption: ** DSA ** ElGamal ** Elliptic curve cryptography ** NTRUEncrypt ** RSA * Cryptographic hash functions: ** HMAC: keyed-hash message authentication ** MD5 – Note that there is now a method of generating collisions for MD5 ** RIPEMD-160 ** SHA-1 ** SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512) ** Tiger (TTH), usually used in Tiger tree hashes * Cryptographically secure pseudo-random number generators ** Blum Blum Shub - based on the hardness of factorization ** Fortuna, intended as an improvement on Yarrow algorithm ** Linear feedback shift register ** Yarrow algorithm * Key exchange ** Diffie–Hellman key exchange *Secret sharing, Secret Splitting, Key Splitting, M of N algorithms ** Blakey's Scheme ** Shamir's Scheme * Symmetric (secret key) encryption: ** Advanced Encryption Standard (AES), winner of NIST competition, also known as Rijndael ** Blowfish ** Data Encryption Standard (DES), sometimes DE Algorithm, winner of NBS selection competition, replaced by AES for most purposes ** IDEA ** RC4 (cipher) ** Tiny Encryption Algorithm Digital logic * Boolean minimization ** Quine–McCluskey algorithm: Also called as Q-M algorithm, programmable method for simplyfying the boolean equations. ** Petrick's method: Another algorithm for boolean simplification. ** Espresso heuristic logic minimizer: Fast algorithm for boolean function minimization. Machine learning and statistical classification * ALOPEX: a correlation based machine learning algorithm * Association rule learning: discover interesting relations between variables, used in Data mining ** Apriori algorithm ** Eclat algorithm ** FP-Growth algorithm ** One-attribute-rule ** Zero-attribute-rule * Boosting: Use many weak learners to boost effectiveness ** AdaBoost: adaptive boosting ** BrownBoost:a boosting algorithm that may be robust to noisy datasets ** LogitBoost: logistic regression boosting ** LPBoost: linear programming boosting * Bootstrap aggregating (bagging): technique to improve stability and classification accuracy * Decision Trees ** C4.5 algorithm: an extension to ID3 ** ID3 algorithm (Iterative Dichotomiser 3): Use heuristic to generate small decision trees * k-nearest neighbors (k-NN): a method for classifying objects based on closest training examples in the feature space * Linde–Buzo–Gray algorithm: a vector quantization algorithm used to derive a good codebook * Locality Sensitive Hashing (LSH): a method of performing probabilistic dimension reduction of high-dimensional data. * Neural Network ** Backpropagation: A supervised learning method which requires a teacher that knows, or can calculate, the desired output for any given input ** Hopfield net: a Recurrent neural network in which all connections are symmetric ** Perceptron: the simplest kind of feedforward neural network: a linear classifier. ** Pulse-Coupled Neural Networks (PCNN): neural models proposed by modeling a cat's visual cortex and developed for high-performance biomimetic image processing. ** Radial basis function network: an artificial neural network that uses radial basis functions as activation functions ** Self-organizing map: an unsupervised network that produces a low-dimensional representation of the input space of the training samples * Random forest: classify using many decision trees * Random multinomial logit: classify using repeated multinomial logit analyses * Reinforcement Learning: ** Q-learning: learn an action-value function that gives the expected utility of taking a given action in a given state and following a fixed policy thereafter ** SARSA (State-Action-Reward-State-Action): learn a Markov decision process policy ** Temporal difference learning * Relevance Vector Machine (RVM): similar to SVM, but provides probabilistic classification * Support Vector Machines (SVM): a set of methods which divide multidimensional data by finding a dividing hyperplane with the maximum margin between the two sets ** Structured SVM: allows training of a classifier for general structured output labels. * Winnow algorithm: related to the perceptron, but uses a multiplicative weight-update scheme Programming language theory * C3 linearization: an algorithm used primarily to obtain a consistent linearization of a multiple inheritance hierarchy in object-oriented programming * Chaitin's algorithm: a bottom-up, graph coloring register allocation algorithm that uses cost/degree as its spill metric * Hindley–Milner type inference algorithm * Rete algorithm: an efficient pattern matching algorithm for implementing production rule systems * Sethi-Ullman algorithm: generate optimal code for arithmetic expressions Parsing * CYK algorithm: An O(n3) algorithm for parsing context-free grammars in Chomsky normal form * Earley parser: Another O(n3) algorithm for parsing any context-free grammar * GLR parser:An algorithm for parsing any context-free grammar by Masaru Tomita. It is tuned for deterministic grammars, on which it performs almost linear time and O(n3) in worst case. * Inside-outside algorithm: An O(n3) algorithm for re-estimating production probabilities in probabilistic context-free grammars * LL parser: A relatively simple linear time parsing algorithm for a limited class of context-free grammars * LR parser: A more complex linear time parsing algorithm for a larger class of context-free grammars. Variants: ** Canonical LR parser ** LALR (Look-ahead LR) parser ** Operator-precedence parser ** SLR (Simple LR) parser ** Simple precedence parser * Packrat parser: A linear time parsing algorithm supporting some context-free grammars and parsing expression grammars * Recursive descent parser: A top-down parser suitable for LL(k'') grammars * Shunting yard algorithm: convert an infix-notation math expression to postfix Quantum algorithms * Deutsch-Jozsa algorithm: criterion of balance for Boolean function * Grover's algorithm: provides quadratic speedup for many search problems * Shor's algorithm: provides exponential speedup (relative to currently known non-quantum algorithms) for factoring a number * Simon's algorithm: provides a provably exponential speedup (relative to any non-quantum algorithm) for a black-box problem Theory of computation and automata * Powerset construction: Algorithm to convert nondeterministic automaton to deterministic automaton. * Tarski–Kuratowski algorithm: a non-deterministic algorithm which provides an upper bound for the complexity of formulas in the arithmetical hierarchy and analytical hierarchy Information theory and signal processing Coding theory Error detection and correction * BCH Codes ** Berlekamp–Massey algorithm ** Peterson-Gorenstein-Zierler algorithm ** Reed–Solomon error correction * BCJR algorithm: decoding of error correcting codes defined on trellises (principally convolutional codes) * Forward error correction * Gray code * Hamming codes ** Hamming(7,4): a Hamming code that encodes 4 bits of data into 7 bits by adding 3 parity bits ** Hamming distance: sum number of positions which are different ** Hamming weight (population count): find the number of 1 bits in a binary word * Redundancy checks ** Adler-32 ** Cyclic redundancy check ** Fletcher's checksum ** Longitudinal redundancy check (LRC) ** Luhn algorithm: a method of validating identification numbers ** Luhn mod N algorithm: extension of Luhn to non-numeric characters ** Parity: simple/fast error detection technique ** Verhoeff algorithm Lossless compression algorithms * Burrows-Wheeler transform: preprocessing useful for improving lossless compression * Context tree weighting * Delta encoding: aid to compression of data in which sequential data occurs frequently * Dynamic Markov compression: Compression using predictive arithmetic coding * Dictionary coders ** Byte pair encoding (BPE) ** DEFLATE ** Lempel-Ziv *** LZ77 and LZ78 *** Lempel-Ziv Jeff Bonwick (LZJB) *** Lempel-Ziv-Markov chain-Algorithm (LZMA) *** Lempel-Ziv-Oberhumer (LZO): speed oriented *** Lempel-Ziv-Storer-Szymanski (LZSS) *** Lempel–Ziv–Welch (LZW) *** LZWL: syllable-based variant *** LZX *** Lempel-Ziv Ross Williams (LZRW) * Entropy encoding: coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols ** Arithmetic coding: advanced entropy coding *** Range encoding: same as arithmetic coding, but looked at in a slightly different way ** Huffman coding: simple lossless compression taking advantage of relative character frequencies *** Adaptive Huffman coding: adaptive coding technique based on Huffman coding *** Package-Merge: Optimizes Huffman coding subject to a length restriction on code strings ** Shannon-Fano coding ** Shannon-Fano-Elias coding: precursor to arithmetic encoding http://www.ece.msstate.edu/~fowler/Classes/ECE8813/Handouts/shannon_fano_elias.pdf * Entropy coding with known entropy characteristics ** Golomb coding: form of entropy coding that is optimal for alphabets following geometric distributions ** Rice coding: form of entropy coding that is optimal for alphabets following geometric distributions ** Truncated binary encoding ** Unary coding: code that represents a number n with n ones followed by a zero ** Universal codes: encodes positive integers into binary code words *** Elias delta, gamma, and omega coding *** Exponential-Golomb coding *** Fibonacci coding *** Levenshtein coding * Fast Efficient & Lossless Image Compression System (FELICS): a lossless image compression algorithm * Incremental encoding: delta encoding applied to sequences of strings * Prediction by partial matching (PPM): an adaptive statistical data compression technique based on context modeling and prediction * Run-length encoding: lossless data compression taking advantage of strings of repeated characters * SEQUITUR algorithm: lossless compression by incremental grammar inference on a string Lossy compression algorithms * 3Dc: a lossy data compression algorithm for normal maps * Audio and Speech compression ** A-law algorithm: standard companding algorithm ** Code-excited linear prediction (CELP): low bit-rate speech compression ** Linear predictive coding (LPC): lossy compression by representing the spectral envelope of a digital signal of speech in compressed form ** Mu-law algorithm: standard analog signal compression or companding algorithm ** Warped Linear Predictive Coding (WLPC) * Image Compression ** Block Truncation Coding (BTC): a type of lossy image compression technique for greyscale images ** Embedded Zerotree Wavelet (EZW) ** Fast Cosine Transform algorithms (FCT algorithms): compute Discrete Cosine Transform (DCT) efficiently ** Fractal compression: method used to compress images using fractals ** Set Partitioning in Hierarchical Trees (SPIHT) ** Wavelet compression: form of data compression well suited for image compression (sometimes also video compression and audio compression) * Transform coding: type of data compression for "natural" data like audio signals or photographic images * Vector quantization: technique often used in lossy data compression Digital signal processing * Adaptive-additive algorithm (AA algorithm): find the spatial frequency phase of an observed wave source * Discrete Fourier transform: determines the frequencies contained in a (segment of a) signal ** Bluestein's FFT algorithm ** Bruun's FFT algorithm ** Cooley–Tukey FFT algorithm ** Fast Fourier transform ** Prime-factor FFT algorithm ** Rader's FFT algorithm * Fast folding algorithm: an efficient algorithm for the detection of approximately-periodic events within time series data * Gerchberg–Saxton algorithm: Phase retrieval algorithm for optical planes * Goertzel algorithm: identify a particular frequency component in a signal. Can be used for DTMF digit decoding. * Karplus-Strong string synthesis: physical modelling synthesis to simulate the sound of a hammered or plucked string or some types of percussion Image processing * Connected component labeling: find and label disjoint regions * Dithering and half-toning ** Error diffusion ** Floyd–Steinberg dithering ** Ordered dithering ** Riemersma dithering * Elser Difference-Map Algorithm: a search algorithm for general constraint satisfaction problems. Originally used for X-Ray diffraction microscopy * Feature detection ** Canny edge detector: detect a wide range of edges in images ** Generalised Hough Transform ** Hough transform ** Marr-Hildreth algorithm: an early edge detection algorithm ** SIFT (Scale-invariant feature transform): is an algorithm to detect and describe local features in images. * GrowCut algorithm: an interactive segmentation algorithm * Richardson–Lucy deconvolution: image de-blurring algorithm * Seam carving: content-aware image resizing algorithm Software engineering * Cache algorithms * CHS conversion: converting between disk addressing systems * Double dabble: Convert binary numbers to BCD * Hash Function: convert a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index into an array ** Fowler–Noll–Vo hash function: fast with low collision rate ** Pearson hashing: computes 8 bit value only, optimized for 8 bit computers ** Zobrist hashing: used in the implementation of transposition tables * Unicode Collation Algorithm * Xor swap algorithm: swaps the values of two variables without using a buffer Database algorithms * Algorithms for Recovery and Isolation Exploiting Semantics (ARIES): transaction recovery * Join algorithms ** Block nested loop ** Hash join ** Nested loop join ** Sort-Merge Join Distributed systems algorithms * Bully algorithm: a method for dynamically selecting a coordinator * Byzantine fault tolerance: good fault tolerance. * Clock synchronization ** Berkeley algorithm ** Cristian's algorithm ** Intersection algorithm ** Marzullo's algorithm * Detection of Process Termination ** Dijkstra-Scholten algorithm ** Huang's algorithm * Lamport ordering: a partial ordering of events based on the ''happened-before relation * Mutual exclusion ** Lamport's Distributed Mutual Exclusion Algorithm ** Maekawa's Algorithm ** Raymond's Algorithm ** Ricart-Agrawala Algorithm * Paxos algorithm: a family of protocols for solving consensus in a network of unreliable processors * Snapshot algorithm: record a consistent global state for an asynchronous system * Vector clocks: generate a partial ordering of events in a distributed system and detect causality violations Memory allocation and deallocation algorithms * Buddy memory allocation: Algorithm to allocate memory such that fragmentation is less. * Garbage collectors ** Boehm garbage collector: Conservative garbage collector ** Cheney's algorithm: An improvement on the Semi-space collector ** Generational garbage collector: Fast garbage collectors that segregate memory by age ** Mark-compact algorithm: a combination of the mark-sweep algorithm and Cheney's copying algorithm ** Mark and sweep ** Semi-space collector: An early copying collector * Reference counting Operating systems algorithms * Banker's algorithm: Algorithm used for deadlock avoidance. * Page replacement algorithms: Selecting the victim page under low memory conditions. ** Adaptive replacement cache: better performance than LRU ** Clock with Adaptive Replacement (CAR): is a page replacement algorithm that has performance comparable to Adaptive replacement cache Disk scheduling * Elevator algorithm: Disk scheduling algorithm that works like an elevator. * Shortest seek first: Disk scheduling algorithm to reduce seek time. Networking * Karn's Algorithm: addresses the problem of getting accurate estimates of the round-trip time for messages when using TCP * Luleå algorithm: a technique for storing and searching internet routing tables efficiently * Network congestion ** Exponential backoff ** Nagle's algorithm: improve the efficiency of TCP/IP networks by coalescing packets ** Truncated binary exponential backoff * Traffic shaping and Rate limiting ** Leaky bucket ** Token bucket Process synchronization * Dekker's algorithm * Lamport's Bakery algorithm * Peterson's algorithm Scheduling * Earliest deadline first scheduling * Fair-share scheduling * Least slack time scheduling * List scheduling * Multi level feedback queue * Rate-monotonic scheduling * Round-robin scheduling * Shortest job next * Shortest remaining time * Top-nodes algorithm: resource calendar management See also *Warnsdorff's algorithm *List of data structures * List of algorithm general topics * List of terms relating to algorithms and data structures *Heuristic References * Algorithms de:Liste von Algorithmen et:Algoritmide loend fr:Liste des algorithmes hi:कलन-विधियों की सूची id:Daftar algoritma pt:Anexo:Lista de algoritmos ru:Список алгоритмов sr:Списак алгоритама tg:Рӯихати алгоритмҳо tr:Algoritma listesi uk:Список алгоритмів